package main

/**
* @Author: DengLibin
* @Date: Create in 2023-01-10 14:46:59
* @Description:
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 * @Author: DengLibin
 * @Date: Create in 2023-01-10 14:47:32
 * @Description: 转二叉搜索树 思路 选中间数作为根节点 左边递归 右边递归
 */
func sortedArrayToBST(nums []int) *TreeNode {

	return toTree(nums, 0, len(nums)-1)
}

func toTree(nums []int, start int, end int) *TreeNode {
	if start > end {
		return nil
	}

	centerIndex := (start + end) / 2

	center := nums[centerIndex]
	root := TreeNode{Val: center}

	//递归左边
	root.Left = toTree(nums, start, centerIndex-1)
	//递归右边
	root.Right = toTree(nums, centerIndex+1, end)

	return &root
}
